#include <pthread.h>
#include <iostream>
#include <fstream>
using namespace std;
int G[100][100]; //dlugosci krawedzi G[u][v];
int g[100][100]; //dlugosc najkrotszej sciezki u~>v
int R[100][100]; //macierz kierowania ruchem
const int INF=10001;
int N, M, u, v, w; //N-ilosc wierzcholkow; M-ilosc krawedzi

void setup(){
     for(int i=0; i<N; i++){ // uzupelnianie wartosciami poczatkowymi
        for(int j=0; j<N; j++){
            G[i][j]=INF;
            g[i][j]=INF;
            R[i][j]=-1;
        }
        G[i][i]=0;
        g[i][i]=0;
    }
}
 
void floyd(){ //znajduje najkrotsze sciezki miedzy kazda para wierzcholkow 
w grafie i wypelnia macierz kierowanie ruchem zeby mozna bylo odtworzyc 
przebieg kazdej drogi
    for(int k=0; k<N; k++){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(g[i][j]>g[i][k]+g[k][j]){ //jezeli droga z i do j, 
poprzez wierzcholek posredni k jest krotsza niz aktualnie najkrotsza znana 
trasa i->j to zaktualizuj
                    g[i][j]=g[i][k]+g[k][j];
                    R[i][j]=k; //oznacza to ze idac po sciezce i~>j trzeba 
przejsc przez k
                }
            }
        }
    }
}
 
void droga(int u, int v){ //odtwarza najkrotsza sciezke miedzy danymi 
wierzcholkami wykorzystujac macierz kierowania ruchem
    if(R[u][v]!=-1){ //dopoki nie dojdziemy do zwyklej krawedzi po ktorej 
trzeba wejsc to zchodz rekurencyjnie i wypisuj wierzcholek posredni k
        droga(u, R[u][v]);
        cout<<R[u][v]+1<<" ";
        droga(R[u][v], v);
    }
}

void wczytywanie(fstream &plik1){
//    fstream plik1;
//    plik1.open("dane.txt");
 //   plik1>>u>>u;
    for(int i=0; i<M; i++){
        plik1>>u>>v>>w;
        //cin>>u>>v>>w;
        G[u-1][v-1]=g[u-1][v-1]=w;
        //G[v-1][u-1]=g[v-1][u-1]=w; //zakladamy ze graf jest 
nieskierowany; w przypadku skierowanego usunac ta linijke
    }
   // plik1.close();
}
 
int main(){
    fstream plik;
    plik.open("dane.txt");
    ios_base::sync_with_stdio(0);
    //cin>>N>>M;
    plik>>N>>M;
 //   plik.close();
    setup();

wczytywanie(plik);    
//    for(int i=0; i<M; i++){
//        plik>>u>>v>>w;
        //cin>>u>>v>>w;
//        G[u-1][v-1]=g[u-1][v-1]=w;
        //G[v-1][u-1]=g[v-1][u-1]=w; //zakladamy ze graf jest 
nieskierowany; w przypadku skierowanego usunac ta linijke
//    }
    plik.close();
    floyd();
            // 1. wyswietlanie wybranej sciezki
    int a1,a2;
    cin>>a1>>a2;
    
    cout << a1 << " -> " << a2 << " : " << g[a1-1][a2-1] << endl << a1 <<" 
";
    droga(a1-1,a2-1);
    cout<<a2<<endl;
           // 1. end
           
           // 2. wyswietlanie wszystkich siezek
//    for(int i=0; i<N; i++){
//        for(int j=0; j<N; j++){
//            cout<<i+1<<"->"<<j+1<<" dl. "<<g[i][j]<<", przebieg: 
"<<i+1<<" ";
//            droga(i, j);
//            cout<<j+1<<endl;
//        }
//    }
          // 2.end
//    system("pause");
    return 0;
}
/* dane wejsciowe - przyklad

5 10
1 2 10
1 5 5
2 3 1
2 5 2
3 4 4
4 3 6
4 1 7
5 2 3
5 3 9
5 4 2

*/
